# JZ8 跳台阶
#
# 描述
# 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
# 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
# 示例1
# 输入：
# 2
# 返回值：
# 2
# 示例2
# 输入：
# 7
# 返回值：
# 21

# 核心代码模式
# -*- coding:utf-8 -*-
# 可以把n级台阶时的跳法看成是n的函数，记为f(n)。
# 当n>2时，第一次跳的时候就有两种不同的选择：
# 一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1);
# 另一种选择是第一次跳2级，此时跳法数目等于后面剩下n-2级台阶的跳法数目，即为f(n-2)。
# 因此，n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。
# f(0)=f(1)=1
# 分析到这里，不难看出这实际上就是斐波那契数列了。
class Solution:
    def jumpFloor(self, n):

        if n<=1: return 1
        # 递归
#         else: return self.jumpFloor(n-1)+self.jumpFloor(n-2)
        #
        # 动态规划
        a = b = 1
        for i in range(2,n+1):
            a,b = b, a+b
        return b



